X3J13 voted in January 1989 <#2882#>MAPPING-DESTRUCTIVE-INTERACTION<#2882#> to restrict side effects during the course of a built-in operation that can execute user-supplied code while traversing a data structure.
Consider the following example:
Depending on the details of the implementation of <#2885#>dolist<#2885#>,
this bit of code could easily print
(which is perhaps what was intended), but it might as easily print
Here is a plausible implementation of <#2890#>dolist<#2890#> that
produces the first result:
But here is a plausible implementation of <#2894#>dolist<#2894#> that
produces the second result:
The X3J13 recognizes and legitimizes varying implementation practices: in general it is an error for code executed during a ``structure-traversing'' operation to destructively modify the structure in a way that might affect the ongoing traversal operation. The committee identified in particular the following special cases.
For list traversal operations, the <#2898#>cdr<#2898#> chain may not be destructively modified.
For array traversal operations, the array may not be adjusted (see <#2899#>adjust-array<#2899#>) and its fill pointer, if any, may not be modified.
For hash table operations (such as <#2900#>with-hash-table-iterator<#2900#> and <#2901#>maphash<#2901#>), new entries may not be added or deleted, <#2902#>except<#2902#> that the very entry being processed by user code may be changed or deleted.
For package symbol operations (for example, <#2903#>with-package-iterator<#2903#> and <#2904#>do-symbols<#2904#>), new symbols may not be interned in, nor symbols uninterned from, the packages being traversed or any packages they use, <#2905#>except<#2905#> that the very symbol being processed by user code may be uninterned.
X3J13 noted that this vote is intended to clarify restrictions on the use of structure traversal operations that are not themselves inherently destructive; for example, it applies to <#2906#>map<#2906#> and <#2907#>dolist<#2907#>. Destructive operators such as <#2908#>delete<#2908#> require even more complicated restrictions and are addressed by a separate proposal.
The X3J13 vote did not specify a complete list of the operations to which these
restrictions apply. Table~#TRAVERSAL-OPERATIONS-TABLE#2909>
In addition, note that user code should not modify list structure that might be undergoing interpretation by the evaluator, whether explicitly invoked via <#2910#>eval<#2910#> or implicitly invoked, for example as in the case of a hook function (a <#2911#>defstruct<#2911#> print function, the value of <#2912#>*evalhook*<#2912#> or <#2913#>*applyhook*<#2913#>, etc.) that happens to be a closure of interpreted code. Similarly, <#2914#>defstruct<#2914#> print functions and other hooks should not perform side effects on data structures being printed or being processed by <#2915#>format<#2915#>, or on a string given to <#2916#>make-string-input-stream<#2916#>. You get the idea; be sensible.
Note that an operation such as <#2917#>mapcar<#2917#> or <#2918#>dolist<#2918#> traverses not only <#2919#>cdr<#2919#> pointers (in order to chase down the list) but also <#2920#>car<#2920#> pointers (in order to obtain the elements themselves). The restriction against modification appears to apply to all these pointers.